'''
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。
 

示例 1：


输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-a-2d-matrix-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
'''
class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """

        def binay_search(nums, target):
            l, r = 0, len(nums) - 1
            while l <= r:
                mid = (l + r) // 2
                if nums[mid] == target:
                    return True
                if nums[mid] < target:
                    l = mid + 1
                if nums[mid] > target:
                    r = mid - 1
            return False

        l_l = len(matrix[0])
        l_r = len(matrix)
        # if l_l >= l_r:
        for line in matrix:
            if line[0] <= target and line[l_l - 1] >= target:
                if binay_search(line, target):
                    return True
        return False
        # else:
        #     for i in range(l_l):
        #         if matrix[0][i] <= target and matrix[l_r - 1][i] >= target:
        #             if binay_search([x[i] for x in matrix], target):
        #                 return True
        #     return False


matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]]
target = 5
Solution().searchMatrix(matrix,target)